package com.mamingchao.foundation.arraysort.selectsort;

/**
 * 升级版
 * 每次循环的时候，把最小的放在最前头；把最大的放在最后头
 * 这样 就能减少一般的循环次数
 *
 * Created by mamingchao on 2020/11/13.
 */
public class SelectSortV2 {
    public static void sort(int[] arr) {
        // check arg array

        if (arr == null || arr.length <2) {
            return;
        }

        for (int i = 0; i < arr.length/2; i++) {
            int minIndex = i;
            int maxIndex = i;

            for (int j = i + 1; j < arr.length - i; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
                maxIndex = arr[j] > arr[maxIndex] ? j : maxIndex;
            }
            swap(arr,minIndex,i);
            if (i + 1 != arr.length - i - 1) {
                swap(arr,maxIndex,arr.length - i - 1);
            }
        }
    }

    private static void swap(int[] arr, int minIndex, int i) {
        int minimum = arr[minIndex];
        arr[minIndex] = arr[i] ;
        arr[i] = minimum;

        // 这里，当 minIndex 与 i 是同一个 值的时候，arr[minIndex]  arr[i] 是数组里的同一个索引位置的值
        //这个 交换算法有bug
        arr[minIndex] = arr[minIndex] + arr[i];
        arr[i] = arr[minIndex] - arr[i];
        arr[minIndex] = arr[minIndex] - arr[i];

    }

    private static void printArray(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        int[] arr = new int[]{5,3,6,1,8,2,1,0};
//        int[] arr = new int[]{7,5,3,4,8,9,2};
        int[] arr = new int[]{7,7,7,4,8,9,7};
              sort(arr);
        printArray(arr);

    }
}
